package graph;

import java.util.LinkedList;
import java.util.Queue;

/**
 *
 * @author wxh
 */
public class bfsTest {

	public void bfs(int s, int t) {

		int v = 10;
		Graph graph = new Graph(v);

		if (s == t) return;
		boolean[] visited = new boolean[v]; //用来记录已经被访问的顶点，避免顶点被重复访问
		visited[s]=true;
		Queue<Integer> queue = new LinkedList(); //queue：存储已经被访问、但相连的顶点还没有被访问的顶点
		queue.add(s);
		int[] prev = new int[v]; //用来记录搜索路径
		for (int i = 0; i < v; ++i) {
			prev[i] = -1;
		}
		while (queue.size() != 0) {
			int w = queue.poll();
			for (int i = 0; i < graph.adj[w].size(); ++i) {
				int q = graph.adj[w].get(i);
				if (!visited[q]) {
					prev[q] = w;
					if (q == t) {
						print(prev, s, t);
						return;
					}
					visited[q] = true;
					queue.add(q);
				}
			}
		}
	}

	private void print(int[] prev, int s, int t) { // 递归打印s->t的路径
		if (prev[t] != -1 && t != s) {
			print(prev, s, prev[t]);
		}
		System.out.print(t + " ");
	}

}